package study.Day_5;

/**
 * @Classname: Day_five_1
 * @Description: leetcode 第五题
 * @Date: 2021/9/29
 * @Author: huwei
 */

/**
 * 题目在Day_five
 */
public class Day_five_1 {
    /**
     * 中心扩展法
     */
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        // 初始化起始位置,截止位置
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 由于字符串长度会出现奇偶问题,所以回文中间字符有可能是一个,也有可能是两个,这里运算两次分别取值i和i+1,
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            // 因为是找最大回文字符串,所以取两个长度的最大值
            int len = Math.max(len1, len2);
            // 获得回文字符串的起始位置,截止位置的下标
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        // 返回回文字符串
        return s.substring(start, end + 1);
    }

    /**
     *
     * @param s     字符串
     * @param left  左边界
     * @param right 右边界
     *
     *  如果left=right那么回文中间字符是一个,如果left!=right那么回文中间字符就是两个
     */
    public int expandAroundCenter(String s, int left, int right) {
        /**
         * 如果左边界大于等于0,右边界小于等于字符串的长度,且左右边界的两个字符串相等,
         * 就把左边界左移一位,右边界右移一位,如此循环可以判断是否是回文字符串,并返回回文字符串长度
         */
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
